//#include<iostream>
//
//using namespace std;
//
//bool validStack(string s)
//{
//	int count = 0;
//	for (int i = 0; i < s.length(); i++)
//	{
//		if (s[i] == 'I')
//			count++;
//		else
//			count--;
//
//		if (count < 0)
//			return false;
//	}
//	if (count == 0)
//		return true;
//	else
//		return false;
//}
//
//
//int main()
//{
//	string s;
//	cout << "please input a string:" << endl;
//	cin >> s;
//	if (validStack(s))
//	{
//		cout << "\nValid\n" << endl;
//	}
//	else
//	{
//		cout << "\nInvalid\n" << endl;
//	}
//	
//	return 0;
//}